﻿#define _CRT_SECURE_NO_WARNINGS 1
//@[Toc](leetcode)
//# 11.最大连续1的个数III（medium）
//[最大连续1的个数III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)
//
//```cpp
//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k) {
//        //翻转最多k个0可以理解为子数组中最多可以存在k个0,用一个变量标记
//        //滑动数组问题
//        //for块进窗口
//        int ret = 0;
//        for (int right = 0, left = 0, count = 0, n = nums.size(); right < n; right++)
//        {
//            if (nums[right] == 0)count++;
//            while (count > k)//出窗口
//            {
//                if (nums[left] == 0)count--;
//                left++;
//            }
//            ret = ret > right - left + 1 ? ret : right - left + 1;
//        }
//        return ret;
//    }
//};
//```
//
//# 12. 将x减到0的最小操作数(medium)
//[将x减到0的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/)
//```cpp
//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x) {
//        //题目要求x减去两端区间减到0，要求区间中的元素最少
//        //这道题难点在两端区间并不一定是一个连续的区间，但是我们可以转化成一个连续区间
//        //对数组求和减去x就是中间区间的值，中间区间是一个连续的空间
//        //这样就可以使用滑动窗口方法
//        int sum = 0;
//        int ret = -1;
//        int n = nums.size();
//        for (auto ch : nums)
//            sum += ch;
//        int target = sum - x;
//        if (target < 0)
//            return -1;
//        for (int left = 0, right = 0, sub_sum = 0; right < n; right++)
//        {
//            sub_sum += nums[right];
//            while (sub_sum > target)
//            {
//                sub_sum -= nums[left];
//                left++;
//            }
//            if (sub_sum == target)
//                ret = ret > right - left + 1 ? ret : right - left + 1;
//        }
//        return ret == -1 ? -1 : n - ret;
//    }
//};
//```
//# 13. 水果成篮（medium)
//[水果成篮](https://leetcode.cn/problems/fruit-into-baskets/submissions/573676020/)
//```cpp
//class Solution {
//public:
//    int totalFruit(vector<int>& fruits) {
//        //数组中的元素代表了元素种类
//        //子数组当中应该只有两种元素才能入篮
//        //多于两种元素则要出篮
//        //滑动数组问题
//        //考虑到同种种类的水果有多个，出窗口要将水果个数全出种类才减少
//        //使用哈希表
//        //数组模拟哈希表
//        int hash[100000] = { 0 };
//        int len = 0;
//        for (int left = 0, right = 0, kind = 0; right < fruits.size(); right++)
//        {
//            if (hash[fruits[right]] == 0)
//                kind++;
//            hash[fruits[right]]++;
//            while (kind > 2)
//            {
//                hash[fruits[left]]--;
//                if (hash[fruits[left]] == 0)
//                    kind--;
//                left++;
//            }
//            len = len > right - left + 1 ? len : right - left + 1;
//        }
//        return len;
//    }
//};
//```
//
//
//# 14. 找到字符串中所有字母异位词（medium）
//[找到字符串中所有字母异位词](https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/)
//
//```cpp
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p) {
//        //滑动窗口问题，不过窗口大小事固定的
//        //难点在于判断
//        vector<int> ret;
//        int hash1[26] = { 0 };
//        int hash2[26] = { 0 };
//        for (auto ch : p)
//            hash1[ch - 'a']++;
//        //简单来说就是当区间子串元素个数等于p的个数时，进行for循环的判断（这里是线性的因为字符只有二十六种）
//        //否则不断进出窗口
//        for (int right = 0, left = 0; right < s.size(); right++)
//        {
//            hash2[s[right] - 'a']++;
//            while (right - left + 1 > p.size())
//            {
//                hash2[s[left] - 'a']--;
//                left++;
//            }
//            for (int i = 0; i < 26; i++)
//            {
//                if (hash1[i] != hash2[i])
//                    break;
//                else if (i == 25)
//                    ret.push_back(left);
//            }
//        }
//        return ret;
//    }
//};
//```
//
//
//# 15. 串联所有单词的⼦串（hard）
//[串联所有单词的⼦串](https://leetcode.cn/problems/substring-with-concatenation-of-all-words/)
//
//```cpp
//class Solution {
//public:
//    vector<int> findSubstring(string s, vector<string>& words) {
//        vector<int> ret;
//        map<string, int>src;
//        for (auto s : words)
//            src[s]++;
//        int gap = words[0].size(), group = words.size();
//        for (int i = 0; i < gap; i++)
//        {
//            map<string, int>des;
//            for (int left = i, right = i, count = 0; right + gap <= s.size(); right += gap)
//            {
//                string in = s.substr(right, gap);
//                des[in]++;
//                if (des[in] <= src[in])count++;
//                if (right - left + 1 > gap * group)
//                {
//                    string out = s.substr(left, gap);
//                    if (des[out] <= src[out])count--;
//                    des[out]--;
//                    left += gap;
//                }
//                if (count == group)
//                    ret.push_back(left);
//            }
//        }
//        return ret;
//    }
//};
//```